//
//  NSArray+ZXCategory.h
//  MobileCaiLocal
//
//  Created by simon on 2020/6/4.
//  Copyright © 2020 com.Chs. All rights reserved.
//
//  2020.07.04 增加map方法，forEach方法；
//  2020.9.2 注释，满足条件的系统方法；以后多用；
//  2021.08.17 修改map方法的bug
//  2023.3.13 增加集合七大排序算法：冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序、归并排序

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN


@interface NSArray<ObjectType> (ZXCategory)


/**
循环遍历集合，返回满足函数条件的组成的新集合；返回一个新的惰性 [Iterable]，其中包含所有满足谓词[test]的元素。
@param testBlock myBlock description
-----系统方法：返回数组中满足给定block函数的对象的索引集合；
block函数满足条件返回YES的对象，会被加入索引集合最后返回；
 - (NSIndexSet *)indexesOfObjectsPassingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))predicate;
 */
- (NSArray *)zx_where:(BOOL(^)(id obj))testBlock;


/// 返回一个新的集合，其中的元素是通过按迭代顺序在这个集合的每个元素上调用' fBlock '函数创建的。
/// 一般用于创建返回新的对象类型集合，或者每个对象修改后的集合；
/// @param fBlock 让每个元素调用函数方法并修改return返回；
- (id)zx_map:(id(^)(id obj))fBlock;




/**
检查此集合的每个元素（全部）是否满足条件[test]；
循环遍历检查集合顺序中的每个元素，如果其中任何一个使[test]返回'false'，则返回'false'，否则返回'true'。
例如：
//检查是否每个item被选中，即是否被全部选中
- (BOOL)getIsSelectedAllGoods
{
    BOOL flag = [self.shopCartModel.list zx_every:^BOOL(CHSShopCartModel_ListModel *  _Nonnull obj) {
        return obj.isSelected;
    }];
    return flag;
}
 */
- (BOOL)zx_every:(BOOL(^)(id obj))testBlock;



/**
  检查此可迭代集合的任何一个元素是否满足[test]，只要其中任何一个使[test]返回'true'，则停止遍历，返回'true'，否则返回false。即循环遍历集合，只要集合里面有一个满足条件的就停止遍历，返回true.
 例如：
 ///检查是否any一个有选中的；
 - (BOOL)getIsAnySelectedFromAllGoods
 {
     BOOL flag = [self.shopCartModel.list zx_any:^BOOL(CHSShopCartModel_ListModel *  _Nonnull obj) {
         return obj.isSelected;
     }];
     return flag;
 }
 ----系统方法：返回数组中满足给定block函数的第一个对象的索引。检查数组中任何一个对象是否满足block函数，只要其中任何一个使block返回YES，则返回YES-返回满足的第一个索引；如果没有满足条件的则返回NO，索引返回NSNotFound。
 - (NSUInteger)indexOfObjectPassingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))predicate;
 */
- (BOOL)zx_any:(BOOL(^)(id obj))testBlock;


/// 将函数fBlock按迭代顺序应用于此集合的每个元素。就是for...in语句；
/// 例如：全选(遍历每个item，并选中),全不选；
/// @param fBlock 一个block
- (void)zx_forEach:(void(^)(id obj))fBlock;

/// 是否为空
- (BOOL)zx_isEmpty;


#pragma mark - 查找算法

#pragma mark-二分查找
///二分查找：需要数组事先被排序，时间复杂度只有O(log n)

/// 二分查找是否包含数字
/// @param obj 查找的对象，此对象是字符串格式或number格式的数字。
- (BOOL)zx_binarySearchWithNumber:(id)obj;


/// 二分查找是否包含对象；
/// @param obj 查找的对象
/// @param cmp obj与中间对象的比较结果的返回函数;obj1是obj，obj2是中间对象
- (BOOL)zx_binarySearchWithObject:(id)obj usingComparator:(NSComparator NS_NOESCAPE)cmp;

/// 二分查找数字所在的索引:可以用系统的二分查找对象所在的索引[-indexOfObject:inSortedRange:options:usingComparator:]
/// @param obj 查找的对象
- (NSInteger)zx_binarySearchIndexOfObjectNumber:(id)obj;


#pragma mark-插值查找
///插值查找：基于二分查找，要求查找表是顺序存储的有序表外，还要求查找表中的元素分布比较均匀

/// 插值查找是否包含数字
/// @param obj 查找的对象，此对象是字符串格式或number格式的数字。
- (BOOL)zx_interpolationSearchWithNumber:(id)obj;


#pragma mark - 排序算法
///系统只支持升序
///- (NSArray<ObjectType> *)sortedArrayUsingFunction:(NSInteger (NS_NOESCAPE *)(ObjectType, ObjectType, void * _Nullable))comparator context:(nullable void *)context;
///- (NSArray<ObjectType> *)sortedArrayUsingFunction:(NSInteger (NS_NOESCAPE *)(ObjectType, ObjectType, void * _Nullable))comparator context:(nullable void *)context hint:(nullable NSData *)hint;
///- (NSArray<ObjectType> *)sortedArrayUsingSelector:(SEL)comparator;
///- (NSArray<ObjectType> *)sortedArrayUsingComparator:(NSComparator NS_NOESCAPE)cmptr API_AVAILABLE(macos(10.6), ios(4.0), watchos(2.0), tvos(9.0));
///- (NSArray<ObjectType> *)sortedArrayWithOptions:(NSSortOptions)opts usingComparator:(NSComparator NS_NOESCAPE)cmptr API_AVAILABLE(macos(10.6), ios(4.0), watchos(2.0), tvos(9.0));

#pragma mark-冒泡排序
/// 冒泡排序：每一轮排序后会把最大（或最小）值交换到最后 1.从第一个开始比较相邻的元素，如果顺序错误就进行交换。2.以此类推，从前往后对每一对相邻的元素进行比较和交换，完成后，最大（或最小）的元素会被移动到最后，此时最后一个元素变成已排序元素。3.除了已排序元素，继续从前往后对每对元素进行比较排序。4.当进行完第n-1趟时，所有记录有序排列，算法执行结束。
/// @param orderType 排序方式，0:升序方式;1:降序方式
/// @param cmptr 比较结果block
/// 例如：
/// NSArray *anArr = @[@4,@1,@0,@0.5,@3,@6,@12,@2];
/// NSArray *sortedArray;
/// sortedArray = [anArr zx_bubbleSort:0 usingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
///     if ([obj1 isKindOfClass:[NSString class]]) {
///         return [obj1 compare:obj2 options:NSNumericSearch];
///     }
///     return [obj1 compare:obj2];
/// }];
- (NSArray *)zx_bubbleSort:(int)orderType
           usingComparator:(NSComparator NS_NOESCAPE)cmptr;


#pragma mark-选择排序
/// 选择排序:每一轮排序后会选择最小（大）的元素放在最前;(1)从数组中选出最小的元素，将其与第一个元素进行交换，此时第一个元素变成已排序元素。(2)依次对数组中的未排序元素进行第一步中的操作。(3)直到数组中所有的元素都变成已排序元素。
/// @param orderType 排序方式，0:升序方式;1:降序方式
/// @param cmptr 比较结果block
- (NSArray *)zx_selectSort:(int)orderType
           usingComparator:(NSComparator NS_NOESCAPE)cmptr;

#pragma mark-插入排序
/// 插入排序：将数组分为两部分，一部分有序，另外一部分无序，从第二个开始将未排序的元素一个个地插入到已经排好序的有序集合的正确位置上，插入时把前面已经排好序的有序集合遍历一遍，找到正确位置后插入并进行移动。
/// @param orderType 排序方式，0:升序方式;1:降序方式
/// @param cmptr 比较结果block
- (NSArray *)zx_insetSort:(int)orderType
          usingComparator:(NSComparator NS_NOESCAPE)cmptr;
- (NSArray *)zx_insetSort:(int)orderType
                      low:(int)low
                     high:(int)high
          usingComparator:(NSComparator NS_NOESCAPE)cmptr;

#pragma mark-希尔排序
/// 希尔排序：希尔排序是对插入排序的改进，也叫缩小增量排序。在处理大量元素的数组排序时，希尔排序能保持更好的排序效率。插入排序是通过逐个对数组元素进行插入来将数组有序化。希尔排序是先选定一个特定的步长，将数组根据步长分割成多个子数组，对每个子数组先使用插入排序进行排序，之后逐步减小步长（减少子数组的个数），直到整个完整数组有序，即直到只比较相邻元素的最后一趟排序为止。
/// @param orderType 排序方式，0:升序方式;1:降序方式
/// @param cmptr 比较结果block
- (NSArray *)zx_shellSort:(int)orderType
          usingComparator:(NSComparator NS_NOESCAPE)cmptr;


#pragma mark-快速排序
/// 快速排序:性能最好，官方方式。快速排序的核心是先寻找一个基准元素，再通过一趟排序将元素分割成独立的两部分，其中，一部分（后半区）的元素都大于基准元素，另一部分（前半区）的元素都小于基准元素。然后按此方法再分别对这两部分元素进行分割，整个排序过程递归进行，直到各个子数组中都只剩下一个元素为止，排序完成。优化：(1)递归比较消耗资源:设置阈值,在数组元素较少时不再递归，而是采用插入排序。(2)基准值取值:三位取中法
- (NSArray <ObjectType>*)zx_quickSortUsingComparator:(NSComparisonResult(^)(id obj, id key))cmptr;
+ (NSArray *)zx_quickSort:(NSArray *)array
          usingComparator:(NSComparisonResult(^)(id obj, id key))cmptr;

///快速排序:非官方方式
+ (NSArray *)zx_quickSort2:(NSArray *)array
           usingComparator:(NSComparisonResult(^)(id obj, id key))cmptr;


#pragma mark-堆排序


/// 堆排序算法（对于最大堆），就是先构造最大堆，之后将顶部的元素取出，再构造最大堆，依次进行，直到数组中的元素排序完成。
/// 堆排序是利用堆这种数据结构设计的排序算法。堆实际上是一种完全二叉树，通过数组的索引关系可以快速定位堆中某个节点的子节点。完全二叉树可以通过一个节点在数组中的下标方便地获取左、右子节点。例如，下标为i的元素，其左子树的下标为(i*2+1)，右子树的下标为(i*2+2)，凭借这种性质，我们可以将数组方便地构造为堆。对于最大堆的构造，通过逆序遍历数组，每次将最大值上浮到父节点中即可。
/// @param array 原数组
/// @param cmptr cmptr description
+ (NSArray *)zx_heapSort:(NSArray *)array
         usingComparator:(NSComparisonResult(^)(id obj1, id obj2))cmptr;

#pragma mark - 归并排序


/// 归并排序算法:采用了递归与合并的思想。其核心是将数组分割成两个子数组，让子数组有序，之后再合并两个有序的子数组到最终的结果数组中去。可以采用二分的方式进行子数组的分割，递归进行，当子数组中只剩下一个元素时，其本身就变成了有序数组，之后只需要根据递归的逻辑一层一层向上合并即可。
/// @param array array对象，可以是任何对象；
/// @param cmptr cmptr description
+ (NSArray *)zx_mergeSort:(NSArray *)array
          usingComparator:(NSComparisonResult(^)(id obj1, id obj2))cmptr;


///  归并排序算法对数字的排序
///  NSArray *anArr =@[@4,@1,@0,@3,@6];
///  NSArray *array = [NSArray zx_mergeSort:anArr];
/// @param array 数组
+ (NSArray *)zx_mergeSort:(NSArray<NSNumber *> *)array;

@end


NS_ASSUME_NONNULL_END

#pragma mark - C方法

///用__bridge方式会报错，需要用纯c方式

/// 冒泡排序：每一轮排序后会把最大（或最小）值交换到最后 1.从第一个开始比较相邻的元素，如果顺序错误就进行交换。2.以此类推，从前往后对每一对相邻的元素进行比较和交换，完成后，最大（或最小）的元素会被移动到最后，此时最后一个元素变成已排序元素。3.除了已排序元素，继续从前往后对每对元素进行比较排序。4.当进行完第n-1趟时，所有记录有序排列，算法执行结束。
/// 例如：int objects[] = {4,1,0,3,6};
/// zx_bubbleSort(objects, 4, 0);
/// @param n 数组数量
/// @param orderType 排序方式，0:升序方式;1:降序方式
void zx_bubbleSort(int data[_Nullable],int n,int orderType);


/// 选择排序:每一轮排序后会选择最小（大）的元素放在最前;(1)从数组中选出最小的元素，将其与第一个元素进行交换，此时第一个元素变成已排序元素。(2)依次对数组中的未排序元素进行第一步中的操作。(3)直到数组中所有的元素都变成已排序元素。
/// @param n 数组数量
/// @param orderType 排序方式，0:升序方式;1:降序方式
void zx_selectSort(int data[_Nullable],int n,int orderType);

/// 插入排序：将数组分为两部分，一部分有序，另外一部分无序，从第二个开始将未排序的元素一个个地插入到已经排好序的有序集合的正确位置上。插入时把前面已经排好序的有序集合遍历一遍，找到正确位置后插入并进行移动。例：对整形数组进行非递减排序。
/// @param n 数组数量
void zx_insetSort(int data[_Nullable],int n);


/// 希尔排序：希尔排序是对插入排序的改进，也叫缩小增量排序。在处理大量元素的数组排序时，希尔排序能保持更好的排序效率。插入排序是通过逐个对数组元素进行插入来将数组有序化。希尔排序是先选定一个特定的步长，将数组根据步长分割成多个子数组，对每个子数组先使用插入排序进行排序，之后逐步减小步长（减少子数组的个数），直到整个完整数组有序，即直到只比较相邻元素的最后一趟排序为止。
/// @param n data[]数组数量
/// @param delta 包含长度为m且递减有序的增量序列，且序列最后一个元素为1,例如[5，3，1]
/// @param m 增量序列数组delta[]长度
void zx_shellSort(int data[_Nullable],int n, int delta[_Nullable],int m);



/// 快速排序:综合性能最好。快速排序的核心是先寻找一个基准元素，再通过一趟排序将元素分割成独立的两部分，其中，一部分（后半区）的元素都大于基准元素，另一部分（前半区）的元素都小于基准元素。然后按此方法再分别对这两部分元素进行分割，整个排序过程递归进行，直到各个子数组中都只剩下一个元素为止，排序完成。优化：(1)递归比较消耗资源:设置阈值,在数组元素较少时不再递归，而是采用插入排序。(2)基准值取值:三位取中法
/// 对整形数组进行非递减拍下
/// @param low 最小索引
/// @param high 最大索引
void zx_quickSort(int data[_Nullable],int low, int high);


/// 归并排序：对data[s..t]进行归并排序。采用了递归与合并的思想。其核心是将数组分割成两个子数组，让子数组有序，之后再合并两个有序的子数组到最终的结果数组中去。可以采用二分的方式进行子数组的分割，递归进行，当子数组中只剩下一个元素时，其本身就变成了有序数组，之后只需要根据递归的逻辑一层一层向上合并即可。
/// @param s 最小索引
/// @param t 最大索引
/// 例如：int objects[] = {4,1,0,3,6};zx_mergeSort(objects, 0, 4);
void zx_mergeSort(int data[_Nullable],int s, int t);
